package _18_剑指OfferII;

import java.util.Arrays;
import java.util.Random;

public class _071_剑指OfferII按权重生成随机数 {

    public static void main(String[] args) {


        int[] res = {1, 3};
        _071_剑指OfferII按权重生成随机数 v = new _071_剑指OfferII按权重生成随机数(res);

        System.out.println(v.pickIndex());
    }

    int[] pre;

    int total;

    Random random;

    public _071_剑指OfferII按权重生成随机数(int[] w) {
        pre = new int[w.length];
        random = new Random();
        // 存储前缀和
        pre[0] = w[0];
        for (int i = 1; i < w.length; ++i) {
            pre[i] = pre[i - 1] + w[i];
        }
        total = pre[w.length - 1];
    }

    public int pickIndex() {
        return binarySearchIndex(random.nextInt(total) + 1);
    }

    // 二分查找前缀和区间长度, 获得概率统计
    private int binarySearchIndex(int num) {
        int begin = 0;
        int end = pre.length - 1;
        while (begin <= end) {
            int mid = begin + ((end - begin) >> 1);
            if (pre[mid] > num) {
                end = mid - 1;
            } else if (pre[mid] < num){
                begin = mid + 1;
            } else {
                return mid;
            }
        }
        return begin;
    }


}
